package leetcode.string.palindrome;

/**
 * 647. 回文子串
 *
 * 字符串中 回文子串的数目
 *
 */
public class CountSubstrings {

    public static void main(String[] args) {
        CountSubstrings solution = new CountSubstrings();
        int count = solution.countSubstrings("aaa");
        System.out.println(count);
    }


    /**
     * 中心扩展法
     *
     * @param s 字符串
     * @return
     */
    public int countSubstrings(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        int count = 0;

        // 奇数回文子串和偶数回文子串不会重复计算, 两者不冲突, 因为子串的长度不一样
        for (int i = 0; i < n; i++) {
            // 奇数回文子串 子串的长度是奇数
            int count1 = expandAroundCenter(s, i, i);
            count = count + count1;

            // 偶数回文子串 子串的长度是偶数
            if (i < n - 1 && chars[i + 1] == chars[i]) {
                // 偶数回文串
                int count2 = expandAroundCenter(s, i, i + 1);
                count = count + count2;
            }
        }
        return count;
    }


    /**
     * 以指定的单个字符或者多个字符为中心, 查找回文子串的个数
     *
     * @param s     字符串
     * @param left  左指针
     * @param right 右指针
     * @return
     */
    public int expandAroundCenter(String s, int left, int right) {
        int count = 0;
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            --left;
            ++right;
            count++;
        }
        return count;
    }
}
